package monotonous_queue;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 柱状图中最大的矩形 <br />
 * 算法：单调栈 <br />
 * 通过单调栈确定柱子的左右边界 <br />
 * 左边界：左边第一个小于柱子高度的位置 <br />
 * 右边界：右边第一个小于柱子高度的位置
 *
 * @author yezh
 * @date 2023/8/16 14:21
 */
public class _84 {

    public static int largestRectangleArea(int[] heights) {
        int n = heights.length, ans = 0;
        // l - 左边第一个比 heights[i] 矮的位置; r - 右边第一个比 heights[i] 矮的位置;
        int[] l = new int[n], r = new int[n];
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            r[i] = n;
            while (!stack.isEmpty() && heights[i] < heights[stack.peekLast()]) r[stack.pollLast()] = i;
            stack.addLast(i);
        }
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            l[i] = -1;
            while (!stack.isEmpty() && heights[i] < heights[stack.peekLast()]) l[stack.pollLast()] = i;
            stack.addLast(i);
        }
        for (int i = 0; i < n; i++) ans = Math.max(ans, heights[i] * (r[i] - l[i] - 1));
        return ans;
    }

}
